#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static int compar_int(const void *a, const void *b) {
  return *(const int *)a - *(const int *)b;
}
// 二分查找最近已经写过两次了，这次试着查找任意类型
void *bsearch_any(const void *key, const void *base, size_t nmemb, size_t size,
                  int (*compar)(const void *, const void *)) {
  // 思考一下，我们首先需要left 、right、mid；
  char *left = (char *)base;
  char *right = (char *)base + (nmemb - 1) * size;
  // 那么mid应该怎么获取呢；直接相加除2能得到正确的mid么?
  // 不对不对，我已经知道整个空间的元素个数了，只需要加上整个空间一半的大小就可以了
  char *mid;
  size_t tempn = nmemb;
  // 接下来是循环
  int com_result;
  // 找了半天原来是循环条件，left<right时 循环结束left
  // 和right指向同一个位置但是整个位置是没被检查过的，疏忽了。
  while (left <= right) {
    // 死循环了,我知道了！ 因为mid赋值的时候使用了nmemb而nmemb是没有更新过的！
    // mid = left + nmemb / 2 * size;
    // 但是这样写tempn是unsigned long 精度有可能会影响结果吧  果然
    // mid = left + tempn / 2 * size;
    // tempn /= 2;
    // 还是不行 输出了一个负数
    tempn = (right - left) / size;
    mid = left + tempn / 2 * size;
    com_result = compar(mid, key);
    if (com_result == 0) {
      return mid;
    } else if (com_result > 0) {
      right = mid - size;
    } else {

      left = mid + size;
    }
  }
  // 如果程序没有在循环中return代表，根本就没有整个元素
  return NULL;
}

// int count = 0;
void qsort_any(void *base, size_t nmemb, size_t size,
               int (*compar)(const void *, const void *)) {
  // 递归出口
  if (nmemb <= 1) {
    return;
  }
  void *bptr = malloc(size);
  void *temp = malloc(size);
  memcpy(bptr, base, size);
  char *left = (char *)base;
  char *right = (char *)base + (nmemb - 1) * size;

  // printf("%d为基准\n", *(int *)bptr);
  while (left < right) {
    // 找到了第一个错误：compar判断时应该包括等于零的情况
    while (left < right && compar(right, bptr) >= 0) {
      // printf("right move\n");
      right -= size;
    }
    while (left < right && compar(left, bptr) <= 0) {
      // printf("left move\n");
      left += size;
    }
    if (left < right) {
      memcpy(temp, right, size);
      memcpy(right, left, size);
      memcpy(left, temp, size);
      // printf("第%d次交换:%d   %d\n", ++count, *(int *)right, *(int *)left);
    }
  }
  // ERROR2：这里将基准赋值给left会使left的元素丢失，应该是交换！！！！
  // memcpy(left, bptr, size);
  // 错误3:我靠我找到了，这里的bptr是深拷贝出来的临时变量，应该将left和base交换而不是bptr和left交换，运行成功！

  // printf("第%d次交换:%d   %d\n", ++count, *(int *)bptr, *(int *)left);
  memcpy(temp, left, size);
  memcpy(left, base, size);
  memcpy(base, temp, size);
  free(bptr);
  free(temp);

  // 接下来是递归了，但是我认为这种递归是极难的，因为寻常写会将上下界传入参数的
  // 计算左边区间元素的个数
  size_t left_nmemb = (left - (char *)base) / size;
  qsort_any(base, left_nmemb, size, compar);

  size_t right_nmemb = nmemb - left_nmemb - 1;
  qsort_any(left + size, right_nmemb, size, compar);
}

int main(int argc, char *argv[]) {
  int nums[10] = {2, 6, 4, 6, 4, 5, 2, 8, 6, 3};
  qsort_any(nums, sizeof(nums) / sizeof(int), sizeof(int), compar_int);
  for (int i = 0; i < sizeof(nums) / sizeof(int); i++) {
    printf("%d   ", nums[i]);
  }
  putchar('\n');

  int key = 8;
  int pos = (int *)bsearch_any(&key, nums, 10, sizeof(int), compar_int) - nums;
  if (nums[pos] == 8) {
    printf("YES");
  }
  printf("%d", pos);
  return 0;
}

/**
 *5 3 1 7 9 0
 *1 3 5 7 9
 *
 */
